import java.awt.*;
import java.awt.geom.Point2D;
import java.util.*;

/**
 * Library of methods associated with a basic Sudoku. 
 * These include basic methods to convert between coordinates and cells or super cell structure
 * Other methods are associated with the overall grid, such as if it is full or the end game status.
 * Individual checks also exist on the legality of a number, i.e. if it is a valid solution to a cell.
 * Methods also exist to generate random seed values and the unique Sudoku solution based on these
 */
public class SudokuLibrary
{
    public static boolean isPointInRect(Point2D p, Rectangle r)
    {
            return (p.getX() >= r.getMinX() && p.getX() < r.getMaxX() && p.getY() >= r.getMinY() && p.getY() < r.getMaxY());
    }

    /**
     * @param p Point of interest
     * @return Coordinates of point
     */
    public static Point convertFromXYToSC(Point p)
    {
        int scCol = p.x / SudokuFrontEnd.noSuperCellColumns;
        int scRow = p.y / SudokuFrontEnd.noSuperCellRows;
        int sc = scRow * SudokuFrontEnd.noSuperCellColumns + scCol;
        int cRow = p.y % SudokuFrontEnd.noCellRows;
        int cCol = p.x % SudokuFrontEnd.noCellColumns;
        int c = cRow * SudokuFrontEnd.noCellRows + cCol;
        return new Point(sc, c);
    }
    
    /**
     * @param p Point of interest
     * @return p Converted p
     */
    public static Point convertFromSCToXY(Point p)
    {
        int xSC = p.x % SudokuFrontEnd.noSuperCellColumns;
        int ySC = p.x / SudokuFrontEnd.noSuperCellRows;
        int xC = p.y % SudokuFrontEnd.noCellColumns;
        int yC = p.y / SudokuFrontEnd.noCellRows;
        return new Point(xSC * SudokuFrontEnd.noSuperCellColumns + xC, ySC * SudokuFrontEnd.noSuperCellRows + yC);
    }
    
    /**
     * Checks if grid is full or not.
     * Returns false if there is a 0, i.e. unfilled value
     * @param grid 2D array of Sudoku cells and their contents
     * @return boolean based on grid is full or not
     */
    public static boolean isFull(int[][] grid)
    {
        for (int x = 0; x < SudokuFrontEnd.colCount; x++)
        {
            for (int y = 0; y < SudokuFrontEnd.rowCount; y++)
            {
                if (grid[x][y] == 0)
                {
                    return false;
                }
            }
        }
        return true;
    }
    
    /**
     * Checks if the grid is solved only when it is full
     * @param grid 2D array of Sudoku cells and their contents
     * @return boolean of win state
     */
    public static boolean isWin(int[][] grid)
    {
        if (isFull(grid))
        {
            return isLegalState(grid);
        }
        return false;
    }
    
    
    /**
     * Checks each super cell, row and column to see if the number presented already exists.
     * @param xy Coordinate point selected
     * @param number Value to be compared for legality
     * @param grid 2D array of Sudoku cells and their contents
     * @return boolean, whether number can fit as a solution or not
     */
    public static boolean isLegal(Point xy, int number, int[][] grid)
    {
        // return false if there are collisions, otherwise true
        // check super cell
        for (int c = 0; c < SudokuFrontEnd.superCellCount; c++)
        {
            Point sc = convertFromXYToSC(xy);
            sc.y = c;
            Point xy2 = convertFromSCToXY(sc);
            if (grid[xy2.x][xy2.y] == number && number != 0 && !xy.equals(xy2))
            {
                return false;
            }
        }
        
        // check row
        for (int x = 0; x < SudokuFrontEnd.colCount; x++)
        {
            if (grid[x][xy.y] == number && number != 0 && !xy.equals(new Point(x, xy.y)))
            {
                return false;
            }
        }
        
        //check columns
        for (int y = 0; y < SudokuFrontEnd.rowCount; y++)
        {
            if (grid[xy.x][y] == number && number != 0 && !xy.equals(new Point(xy.x, y)))
            {
                return false;
            }
        }
        return true;
    }
    
    /**
     * Goes through all cells and checks their legal state.
     * @param grid 2D array of Sudoku cells and their contents
     * @return boolean on whether the grid is a valid solution
     */
    public static boolean isLegalState(int[][] grid)
    {
        for (int x = 0; x < SudokuFrontEnd.colCount; x++)
        {
            for (int y = 0; y < SudokuFrontEnd.rowCount; y++)
            {
                if (!isLegal(new Point(x, y), grid[x][y], grid))
                {
                    return false;
                }
            }
        }
        return true;
    }
    
    /**
     * Generates and places seed values randomly for the solver function to work on
     * @param numFilled Number of cells currently randomly generated
     * @return 2D array of Sudoku cells and their seed contents
     */
    public static int[][] generateRandomGrid(int numFilled)
    {
        // solution must be unique
        // no known 16 hint unique solvable puzzles
        // if bruteforce from 1-9 and 9-1 produce the same grid, then it is unique
        int[][] grid = new int[SudokuFrontEnd.noCellRows * SudokuFrontEnd.noSuperCellRows][SudokuFrontEnd.noCellColumns * SudokuFrontEnd.noSuperCellColumns];

		ArrayList<Point> emptyPoints = new ArrayList<Point>();
		Random r = new Random();
        
        for (int i = 0; i < SudokuFrontEnd.cellCount; i++)
		{
			if (grid[i % SudokuFrontEnd.colCount][i / SudokuFrontEnd.rowCount] == 0)
			{
				emptyPoints.add(new Point(i % SudokuFrontEnd.colCount, i / SudokuFrontEnd.rowCount));
			}
		}
        
		for (int i = 0; i < Math.min(numFilled, emptyPoints.size()); i++)
		{
			int j = r.nextInt(emptyPoints.size());
			Point chosenPoint = emptyPoints.get(j);
			emptyPoints.remove(j);
			for (int k = 1; k < 10; k++)
			{
				if (isLegal(chosenPoint, k, grid))
				{
					grid[chosenPoint.x][chosenPoint.y] = k;
					break;
				}
			} 
		}
        return grid;
    }
    
    /**
     * Checks whether a given Sudoku solution is unique. 
     * @param cell Cell number currently at, or recursion depth level
     * @param grid 2D array of Sudoku cells and their contents
     * @return boolean on whether a unique solution was found
     */
    public static boolean oneUniqueSolution(int cell, int[][] grid)
    {
    	int[][] tempGrid = new int[SudokuFrontEnd.colCount][SudokuFrontEnd.rowCount];
        for (int i = 0; i < grid.length; i++)
		{
			for (int j = 0; j < grid.length; j++)
			{
				tempGrid[i][j] = grid[i][j];
			}
		}
        if (oneUniqueSolution2(cell, tempGrid) == 1)
        {
        	return true;
        }
        else
        {
        	return false;
        }
       
    }
    
    /**
     * A Sudoku solution is unique if there is only one way to permute to that solution.
     * Recursive exhaustive method based on the Solver function.
     * If more than one way of arriving at the solution grid is found, it is not unique
     * @param cell Cell number currently at, or recursion depth level
     * @param grid 2D array of Sudoku cells and their contents
     * @return 1 each time a solution is reached, 0 otherwise
     */
    public static int oneUniqueSolution2(int cell, int[][] grid)
    {
    	int solutionCount = 0;
    	Point p = new Point(cell % SudokuFrontEnd.colCount, cell / SudokuFrontEnd.rowCount);
    	//A solution is reached whenthe depth level has accessed all cells
    	if (cell == SudokuFrontEnd.cellCount)
    	{
    		return 1;
    	}
    	if (grid[p.x][p.y] != 0)
    	{
    		solutionCount += oneUniqueSolution2(cell + 1, grid);
    		if (solutionCount > 1)
    		{
    			return Integer.MAX_VALUE;
    		}
    	}
    	else
    	{
	    	for (int i = 1; i < 10; i++)
	        {
	            if (isLegal(p, i, grid))
	            {
	                grid[p.x][p.y] = i;
	                solutionCount += oneUniqueSolution2(cell + 1, grid);
	        		if (solutionCount > 1)
	        		{
	        			return Integer.MAX_VALUE;
	        		}
	            }
	        }
	    	grid[p.x][p.y] = 0;
    	}
    	return solutionCount;
    }
    
    /**
     * Initialise the Solver function
     * @param c Initial depth value
     * @param grid Grid containing partially filled seed values
     * @return Valid grid of solutions if applicable
     */
    public static int[][] solve(int c, int[][] grid)
    {    
    	//Initialise solution grid with partially filled seed values first
        int[][] tempGrid = new int[SudokuFrontEnd.colCount][SudokuFrontEnd.rowCount];
        for (int i = 0; i < grid.length; i++)
		{
			for (int j = 0; j < grid.length; j++)
			{
				tempGrid[i][j] = grid[i][j];
			}
		}
        //Return the solution grid if it is valid
        if (solve2(c, tempGrid))
        {
        	return tempGrid;
        }
        else
        {
        	return null;
        }
    }
    
    /**
     * Main solver function. Recursively attempts to add a value if no conflict, until all cells are filled
     * @param cell Current recursive depth level equivalent to cell number
     * @param grid 2D array of currently filled Sudoku cells and their contents
     * @return true if a solution is found, false otherwise
     */
    public static boolean solve2(int cell, int[][] grid)
    {
    	Point p = new Point(cell % SudokuFrontEnd.colCount, cell / SudokuFrontEnd.rowCount);
    	//Solution is finished at a depth of 81, i.e. all cells filled.
    	if (cell == SudokuFrontEnd.cellCount)
    	{
    		return true;
    	}
    	//Skip pre-existing values to prevent overwrite by calling solve2 on the next cell
    	if (grid[p.x][p.y] != 0)
    	{
    		return solve2(cell + 1, grid);
    	}
    	//Check if each number is hypothetically valid for a cell
    	for (int i = 1; i < 10; i++)
        {
            if (isLegal(p, i, grid))
            {
            	//If valid, assign the number and call solve2 on the next cell
                grid[p.x][p.y] = i;
                //If next cell returns true, i.e. eventually reaches a solution, return a true for backtrack
                if (solve2(cell + 1, grid))
                {
                    return true;
                }
            }
        }
    	//If no valid numbers for cell, reset to 0 and return false
        grid[p.x][p.y] = 0;
        return false;
    }
}